package com.fr.lintcode;

/**
*作者：furong
*日期：2017年2月6日
*时间：上午10:29:46
*/
public class Q29 {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s1.length() <= 0) {
            if (s2 == null) {
                if (s3 == null) {
                    return true;
                } else {
                    return false;
                }
            } else {
                return s2.equals(s3);
            }
        }
        if (s2 == null || s2.length() <= 0) {
            return s1.equals(s3);
        }
        if (s3 == null || s3.length() <= 0) {
            return false;
        }
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if (l1 + l2 != l3) {
            return false;
        }
        boolean dp[][] = new boolean[l1 + 1][l2 + 1];
        for (int i = 0; i <= l1; i++) {
            for (int j = 0; j <= l2; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(j - 1));
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(i - 1));
                } else {
                    dp[i][j] = (dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(i + j - 1))) || (dp[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(i + j - 1)));
                }
            }
        }
        return dp[l1][l2];
    }
}
